package quwei;

import java.util.Scanner;

public class Test3_4 {

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        System.out.println("请先输入要排序的数据的个数：");
        int N=scanner.nextInt();
        System.out.println("请输入要排序的数字：");
        int[] R=new int[N];
        for(int i=0;i<N;i++)
            R[i]=scanner.nextInt();

        quickSort(R,0,N-1);                                //调用快速排序算法
        System.out.println("排序后的序列为：");
        for(int i=0;i<N;i++)
            System.out.print(R[i]+" ");
    }

    /*快速排序递归算法*/
    public static void quickSort(int[] R,int low,int high) {
        int mid;
        if(low<high) {
            mid=partition(R,low,high);                     //对原序列进行分解，找到基准位置
            quickSort(R,low,mid-1);                        //左区间递归快速排序
            quickSort(R,mid+1,high);                       //右区间递归快速排序
        }
    }

    /*划分函数，找到基准元素的位置*/
    public static int partition(int[] R,int low,int high) {
        int i=low,j=high;
        int pivot=R[low];                                  //取第一个元素做基准
        while(i<j) {
            while(i<j&&R[j]>pivot)                         //从右向左扫描，若R[j]大于基准则继续向左走
                j--;
            if(i<j) {                                      //while循环跳出说明找到一个小于基准的元素
                int temp=R[i];                             //交换元素位置
                R[i]=R[j];
                R[j]=temp;
                i++;
            }
            while(i<j&&R[i]<pivot)                         //从左向右扫描，若R[i]小于基准则继续向右走
                i++;
            if(i<j) {                                      //while跳出循环说明找到一个大于基准的元素
                int temp=R[i];                             //交换位置
                R[i]=R[j];
                R[j]=temp;
                j--;
            }
        }
        return i;
    }
}
